The disclosed invention generally relates to encoding and decoding the Alternant code family. The Alternant code family includes the Goppa, Strivastava, Bose-Chaudhuri-Hocquenghem (BCH), and Reed-Solomon classes of codes. The disclosed invention is particularly directed to techniques for time domain encoding and decoding the linear, cyclic, error correcting codes of the Alternant family, such as the BCH and Reed-Solomon codes.
The transmission of information over a communications channel generally results in a received signal which includes the original information and distortions. Such distortions may result in loss of information content in the received signal and, therefore, errors in the received signal. Various techniques have been developed over the years for the purpose of increasing the probability of error-free transmission.
A particular approach to increasing the probability of error-free transmission has been directed to coding techniques which provide for the detection of errors and, to varying degrees, the correction of some or all detected errors. Such coding techniques generally involve the inclusion of redundant information based on the data to be transmitted. Generally, encoding would involve performing operations on the data to yield a code word which includes the data information and the redundant information.
Encoding and decoding techniques often apply to only one code within a family rather than to all codes within a family. However, in the Alternant code family, the decoder techniques originally developed just for BCH codes also can decode the other code classes within the Alternant family. Therefore, the remaining discussion focuses on BCH codes while being applicable to all members of the Alternant code family.
A well-known approach to decoding BCH codes is set forth in "The Technology of Error Correcting Codes," E. R. Berlekamp,Proceedings of the IEEE, Vol. 68, No. 5, May 1980, p. 588. Disclosed therein is a special purpose microprogrammable Galois Field computer which generally includes an addressing/control unit, a microcode memory unit, and an arithmetic unit.
U.S. Pat. No.4,162,480, issued to Berlekamp on Jul. 24, 1979, is directed to a special purpose Galois Field computer which includes an address generator, a control unit and an arithmetic unit.
U.S. Pat. No.4,251,875, issued to Marver et al. on Feb. 17, 1981, is directed to implementation of Galois multiplication using binary logic devices.
U.S. Pat. No. 4,413,339, issued to Riggle et al. on Nov. 1, 1983, is directed to a system for detecting and correcting multiple errors and utilizes a Reed-Solomon code.
Prior art BCH decoders have utilized frequency domain decoding, time domain decoding, or a mixture of both. The frequency domain algorithm is described in the article "Transform Techniques for Error Control Codes," R. E. Blahut, IBM Journal of Research and Development, Vol. 23, No. 3, May 1979, pp. 229-315. The time domain algorithm is set forth in the article, "Transform Decoding Without Transforms," R. E. Blahut, Tenth Annual IEEE Communication Theory Workshop, Apr. 27-30, 1980.
The prior art BCH decoders are complex and inefficient, requiring extensive and time consuming computations. For example, a first step would include a linear transformation of the received data into syndromes or frequency domain data. The second step would be the computation of the erasure locator polynomial, where an erasure is defined as an error of known location and unknown magnitude. The third step would be the computation of the errata (errors and erasures) locator polynomial using the syndromes and erasure polynomial computed previously. The roots of the errata polynomial locate the errors and are used to solve a set of linear equations for the error values.
While the foregoing conventional decoding algorithm attempts to exploit the algebraic properties of BCH codes, the particular steps require equation solving and extensive programming in order to achieve some form of efficient decoding architecture. Typically, prior art decoders have used programmable processor architectures with limited parallel processing capability and, therefore, limited efficiency.
The prior art decoders also cannot generally accommodate within a single architecture three of the major theoretical options available to algebraic codes. Prior art decoders generally cannot accommodate a variable codeword length and variable information rate within the same implementation. Also, prior art decoders generally cannot accommodate a variety of codes such as all the codes within the Alternant family. Furthermore, prior art decoders generally cannot accommodate codes over a variety of Galois field arithmetic structures.